package com.cat.dataStructure03;

import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/
 * @create 2025/11/19 17:57
 * @since JDK17
 */

public class Solution90 {
    class TreeAncestor {
        static int MAXN = 50001, LIMIT = 16, power, cnt;
        static int log2(int n) {
            int ans = 0;
            while ((1 << ans) <= (n >> 1)) {
                ans++;
            }
            return ans;
        }
        static int[] head = new int[MAXN], next = new int[MAXN], to = new int[MAXN], deep = new int[MAXN];
        static int[][] stjump = new int[MAXN][LIMIT];
        static void addEdge(int u, int v) {
            next[cnt] = head[u];
            to[cnt] = v;
            head[u] = cnt++;
        }

        public TreeAncestor(int n, int[] parent) {
            power = log2(n);
            cnt = 1;
            Arrays.fill(head, 0, n, 0);
            for (int i = 1; i < parent.length; i++) {
                addEdge(parent[i], i);
            }
            dfs(0, 0);
        }
        void dfs(int i, int f) {
            if (i == 0) {
                deep[i] = 1;
            } else {
                deep[i] = deep[f] + 1;
            }
            stjump[i][0] = f;
            for (int p = 1; p <= power; p++) {
                stjump[i][p] = stjump[stjump[i][p - 1]][p - 1];
            }
            for (int e = head[i]; e != 0; e = next[e]) {
                dfs(to[e], i);
            }
        }
        public int getKthAncestor(int node, int k) {
            if (deep[node] <= k) {
                return -1;
            }
            int s = deep[node] - k;
            for (int p = power; p >= 0; p--) {
                if (deep[stjump[node][p]] >= s) {
                    node = stjump[node][p];
                }
            }
            return node;
        }
    }
}
